#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    int findNumberOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp(n), ret(n);
//        int maxlen = 0, ans = 0;
//        for (int i = 0; i < n; i++)
//        {
//            dp[i] = 1;
//            ret[i] = 1;
//            for (int j = 0; j < i; j++)
//            {
//                if (nums[i] > nums[j])
//                {
//                    if (dp[j] + 1 > dp[i])
//                    {
//                        dp[i] = dp[j] + 1;
//                        ret[i] = ret[j];
//                    }
//                    else if (dp[j] + 1 == dp[i])
//                    {
//                        ret[i] += ret[j];
//                    }
//
//                }
//            }
//            if (dp[i] > maxlen)
//            {
//                maxlen = dp[i];
//                ans = ret[i];
//            }
//            else if (maxlen == dp[i])
//                ans += ret[i];
//        }
//        return ans;
//    }
//};

//class Solution {
//public:
//    int findLongestChain(vector<vector<int>>& pairs) {
//        int n = pairs.size();
//        vector<int> dp(n,1);
//        sort(pairs.begin(), pairs.end());
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j < i; j++)
//            {
//                if (pairs[i][0] > pairs[j][1])
//                {
//                    dp[i] = max(dp[j] + 1, dp[i]);
//                }
//            }
//        }
//        return dp[n - 1];
//    }
//}; 

//class Solution {
//public:
//    int longestSubsequence(vector<int>& arr, int difference) {
//        int n = arr.size();
//        vector<int> dp(n, 1);
//        int maxlen = 1;
//        for (int i = 1; i < n; i++)
//        {
//            if ((arr[i] - arr[i - 1]) == abs(difference))
//            {
//                dp[i] = dp[i - 1] + 1;
//            }
//            if (dp[i] > maxlen)
//                maxlen = dp[i];
//        }
//        return maxlen;
//    }
//};

//int main()
//{
//    Solution s;
//    vector<int> arr = { 1,2,3,4 };
//    cout<<s.longestSubsequence(arr,1);
//    return 0;
//}